//
// Created by liushuai on 2021/1/4.
//

#include "longestPalindrome.h"
// no pass
using namespace std;

bool isPalindrome(string s) {
    if (s.size() == 1)
        return true;
    else {
        int head = 0;
        int tail = s.size() - 1;
        while (head <= tail) {
            if (s[head] == s[tail]) {
                tail--;
                head++;
            } else
                return false;
        }
        return true;
    }
}

string longestPalindrome(string s) {
    int size = s.size();
    if (size == 0 || size == 1)
        return s;
    int max_length = 0;
    int index = 0;
    string result = "";

    for (int start = 0; start < size; start++) {
        for (int end = start + 1; end <= size; end++) {
            string substr = s.substr(start, end - start + 1);
            if (isPalindrome(s.substr(start, end - start + 1))) {
                if (substr.size() > max_length) {
                    result = substr;
                    max_length = substr.size();
                }
            }
        }
    }
    return result;
}

int longestPalindrome1(string s) {
    map<char, int> freq;
    int res = 0;
    int count_one = 0;
    for (auto ch:s) {
        if (freq.count(ch))
            freq[ch] += 1;
        else
            freq[ch] = 1;
    }
    for (auto e:freq) {
        if (e.second % 2 == 0)
            res += e.second;
        else {
            res += e.second - 1;
        }
    }
    return s.size() !=res  ? res + 1 : res;

}